package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/check-completeness-of-a-binary-tree/'>二叉树的完全性检验(Check Completeness of a Binary Tree)</a>
 * <p>给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树 。</p>
 * <p>在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 h 层）中可以包含 1 到 2^h 个节点。</p>
 * </p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,3,4,5,6]
 *      输出：true
 *      解释：最后一层前的每一层都是满的（即，节点值为 {1} 和 {2,3} 的两层），且最后一层中的所有节点（{4,5,6}）尽可能靠左。
 *
 * 示例 2：
 *      输入：root = [1,2,3,4,5,null,7]
 *      输出：false
 *      解释：值为 7 的节点不满足条件「节点尽可能靠左」。
 * </pre>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [1, 100] 内</li>
 *     <li>1 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/20 17:27
 */
public class LC0958CheckCompletenessOfBinaryTree_M {

    static class Solution {
        public boolean isCompleteTree(TreeNode root) {
            boolean end = false;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode currNode = queue.poll();
                if (end) {
                    if (currNode.left != null || currNode.right != null) {
                        return false;
                    }
                }
                if (currNode.left != null && currNode.right != null) {
                    queue.offer(currNode.left);
                    queue.offer(currNode.right);
                } else if (currNode.left == null && currNode.right != null) {
                    return false;
                } else {
                    // 左有右空 或 左空右空。到达最后一个节点,end 置为 true
                    // currNode.left != null && currNode.right == null、currNode.left == null && currNode.right == null
                    // 这种状态下，将标志修改为 true，后续出现的所有节点必须为 null
                    end = true;
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                }
            }
            return true;
        }

        public boolean isCompleteTree2(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode currNode = queue.poll();
                if (currNode != null) {
                    queue.offer(currNode.left);
                    queue.offer(currNode.right);
                } else {
                    break;
                }
            }
            while (!queue.isEmpty()) {
                if (queue.poll() != null) {
                    return false;
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.left = new TreeNode(4);
        root1.left.right = new TreeNode(5);
        root1.right.left = new TreeNode(6);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.left.left = new TreeNode(4);
        root2.left.right = new TreeNode(5);
        root2.right.right = new TreeNode(7);

        TreeNode root3 = new TreeNode(1);
        root3.left = new TreeNode(2);
        root3.left.left = new TreeNode(4);

        Solution solution = new Solution();
        //System.out.println(solution.isCompleteTree(root1));
        //System.out.println(solution.isCompleteTree(root2));
        System.out.println(solution.isCompleteTree(root3));

    }
}
